package medium

func generateParenthesis(n int) []string {
	out := new([]string)
	dfs(0, 0, n, "", out)
	return *out
}

func dfs(l, r, max int, str string, out *[]string) {
	if l == r && l == max {
		*out = append(*out, str)
		return
	}
	if l < max {
		dfs(l+1, r, max, str+"(", out)
	}
	if r < l {
		dfs(l, r+1, max, str+")", out)
	}
}
